package algorithms.leaning.class02;

import common.util.MyUtil;

/**
 * 一个数组中有两种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两种数
 *
 * @author guichang
 * @date 2021/5/30
 */

@SuppressWarnings("all")
public class Code4_异或_找数2 {

    public static void main(String[] args) {
        int[] nums = MyUtil.createArray(1, 1, 1, 2, 2, 5, 6, 6, 7, 7, 9, 9, 9, 9, 4, 4, 4, 4, 4, 4);
        int[] search = numberSearch(nums);
        MyUtil.printInt(search);
    }

    public static int[] numberSearch(int[] nums) {
        if (nums == null || nums.length < 2) {
            return null;
        }
        // 先计算数组的异或和，结果就是两个数的异或
        int xorAnd = 0;
        for (int x : nums) {
            xorAnd ^= x;
        }
        // 最右侧的1
        int rightOne = xorAnd & (-xorAnd);
        // 其中一个
        int oneOf = 0;
        for (int x : nums) {
            if ((x & rightOne) == 0) {
                oneOf ^= x;
            }
        }
        // 另一个就是xorAnd异或的结果
        return new int[]{oneOf, xorAnd ^ oneOf};
    }


}